算法 - 2 动态规划

发表于 | 分类于 | | 阅读次数:
字数统计: 1k | 阅读时长 ≈ 4

https://hit-alibaba.github.io/interview/basic/algo/DP.html

动态规划

适用于动态规划的问题，需要满足最优子结构和无后效性，动态规划的求解过程，在于找到状态转移方程，进行自底向上的求解。

爬楼梯问题 LeetCode 70

经典的动态规划问题之一，容易找到其状态转移方程为 dp[i] = dp[i-1] + dp[i-2]，从基础的 1 和 2 个台阶两个状态开始，自底向上求解：

容易看出其实结果就是 fibonacci 数列的第 n 项。

连续子数组的最大和 LeetCode 53

用 dp[n] 表示元素 n 作为末尾的连续序列的最大和，容易想到状态转移方程为dp[n] = max(dp[n-1] + num[n], num[n])，从第 1 个元素开始，自顶向上求解：

House Robber LeetCode 198

对于一个房子，有抢和不抢两种选择，容易得到状态转移方程 dp[i+1] = max(dp[i-1] + nums[i], dp[i])，示例代码如下：

最长回文子串 LeetCode 5

用 dp[i][j] 表示子串 i 到 j 是否是回文，使用动态规划求解：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
string longestPalindrome(string s) {
    int m = s.size();
    if (m == 0) {
        return "";
    }
    vector<vector<int>> dp(m, vector<int>(m, 0));
    int start = 0;
    int length = 1;

    for (int i = 0; i < m; i++) {
        // 单个字符属于回文，例如 abcd
        dp[i][i] = 1;

        // 连续两个字符相同属于回文，例如 abb
        if (i < m - 1) {
            if (s[i] == s[i + 1]) {
                dp[i][i + 1] = 1;
                start = i;
                length = 2;
            }
        }
    }

    for (int len = 2; len <= m; len++) {
        for (int i = 0; i < m - len; i++) {
            int j = i + len;
            // 扩展长度
            if (dp[i + 1][j - 1] == 1 && s[i] == s[j]) {
                dp[i][j] = 1;

                if (j - i + 1 > length) {
                    start = i;
                    length = j - i + 1;
                }
            }
        }
    }

    return s.substr(start, length);
}

最小编辑距离 LeetCode 72

2.进程线程（还有有关操作系统的 我忘了

3.数据库查询 然后连接查询

8.链表讲一下 什么单向链表双向链表循环链表 链表适合快排吗为什么

  1. 四次挥手 time_wait

  2. 客户端当被告知服务端接收窗口大小为0后的行为，如果服务端的接收窗口又变大了呢？

  3. 拥塞控制

https://www.cnblogs.com/logsharing/p/8448446.html

  • get参数通过url传递，post参数放在request body中
  • get参数是有长度限制的，而post没有
  • get参数直接暴露在url中，较为不安全，不能传递敏感信息
  • get请求只能进行url编码，而post支持多种编码方式
  • get请求浏览器会主动cache
  • get请求参数会被完整保留在浏览历史记录里，而post中的参数不会被保留
  • get和post本质上就是TCP链接，并无差别。但是由于HTTP的规定和浏览器/服务器的限制，导致他们在应用过程中体现出一些不同
  • get产生一个TCP数据包，post产生两个TCP数据包

总结：

  1. 对于GET方式的请求，浏览器会把http header和data一并发送出去，服务器响应200（返回数据）；而对于POST，浏览器先发送header，服务器响应100 continue，浏览器再发送data，服务器响应200 ok（返回数据）。（据研究，在网络环境好的情况下，发一次包的时间和发两次包的时间差别基本可以无视。而在网络环境差的情况下，两次包的TCP在验证数据包完整性上，有非常大的优点。）
  2. 对于get和post的区别，get传递数据如同是写在脸上，post传递数据如同放在肚子里，脸上不能放太多东西，也不能放隐私东西，肚子里就无所谓啦~（一个面试官给我说的巧记妙招~）

浏览器输入 www.qq.com 发生了什么; 第二次访问与第一次有什么区别吗，长连接和短连接，四次挥手，客户端先发和服务端先发FIN有什么区别，一般是哪端先发，原因，哪端先发好？time_wait持续时间？2MSL? 没有time_wait有什么问题

http 与 https 区别，ssl 的过程